package offer.day19;

import java.util.LinkedList;

public class No31isPopOrder {
    /*面试题31：栈的压入、弹出序列
     * 题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
     * 假设压入栈的数字均不相等。例如，序列{1，2，3，4，5}是某栈的压栈序列，
     * 序列{4，5，3，2，1}是该压栈序列对应的一个弹出序列，
     * 但{4，3，5，1，2}就不可能是该压栈序列的弹出序列。
     *
     * 思路：*******************判断序列是否为栈的弹出序列，因为题设并没有提到使用栈进行操作，所以这就意味着不一定要使用栈去进行判断（避免误区）
     * 只要能解决问题，使用什么数据结构都是可行的
     * 一层循环模拟push元素压入，注意for中结束条件要保证i<=length,因为有可能要走到最后，才开始出栈的情况
     *         这种情况下，i值会大于1，还要注意push次数应该<length，保证个数正确
     * 第二层循环模拟pop元素弹出，判断list是否为空，若不为空，则比较两个值（出栈序列的第一个值+list的表头值）是否相等，相等则弹出+弹出序列数组向下走，判断两个值是否相等
     * 									否则，则进行压入元素操作。
     *
     * */
    public static void main(String[] args) {
        No31isPopOrder p = new No31isPopOrder();
        //压入序列
        int[] sPush = {1,2,3,4,5};
        //弹出序列
        int[] sPop = {5,4,3,2,1};

        if(p.isPopOrder(sPush,sPop))
            System.out.println("是压入序列的一个弹出序列！");
        else
            System.out.println("不是压入序列的一个弹出序列！！！");

    }

    private boolean isPopOrder(int[] sPush, int[] sPop) {
        if(sPush==null || sPop==null || sPush.length!=sPop.length) return false;
        LinkedList<Integer> list=new LinkedList<>();
        int index=0;
        for(int i=0;i<=sPush.length;i++){
            while(!list.isEmpty()){
                if(list.getFirst()==sPop[index]){
                    list.removeFirst();
                    index++;
                    continue;
                }else{
                    break;
                }
            }
            if(i<sPush.length){
                list.addFirst(sPush[i]);
            }
        }
        if(list.isEmpty()&&sPop.length==index){
            return true;
        }
        return false;
    }
}
